import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA
 * Description:leetcode：20. 有效的括号
 * <a href="https://leetcode.cn/problems/valid-parentheses/">...</a>
 * User: DELL
 * Data: 2023-01-08
 * Time: 20:47
 */


class Solution {
    public boolean isValid(String s) {
        //辅助栈
        Deque<Character> stack = new LinkedList<>();
        int size = s.length();
        for (int i = 0; i < size; i++) {
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') {
                stack.push(ch);
            } else {
                //栈为空
                if (stack.isEmpty()) {
                    return false;
                }
                //核对括号
                char ch2 = stack.pop();
                switch (ch) {
                    case ')':
                        if (ch2 != '(') {
                            return false;
                        }
                        break;
                    case ']':
                        if (ch2 != '[') {
                            return false;
                        }
                        break;
                    case '}':
                        if (ch2 != '{') {
                            return false;
                        }
                        break;
                }
            }
        }
        //这里需要再判断栈是否为空，防止左括号多的情况
        return stack.isEmpty();
    }
}